package com.eatme.core;

public class LinkedList<E> {

    private class Node {

          public E e;

          public  Node next;

          public  Node(E e,Node next) {
              this.e = e;
              this.next = next;
          }

          public Node(E e) {
              this(e,null);
          }

          public Node() {
              this(null,null);
          }

        @Override
        public String toString() {
            return e.toString();
        }
    }

    private Node dummyhead;

    private int size;

    public LinkedList() {
        dummyhead = new Node(null,null);
        size = 0;
    }

    // 获取链表中元素个数
    public int getSize() {
        return size;
    }

    // 返回链表是否为空
    public boolean isEmpty() {
        return size == 0;
    }

    // 在链表头添加新的元素
    public void addFirst(E e) {
        // v1
//        Node node = new Node();
//        node.next =head;
//        head =node;

        // v2
//        head = new Node(e,head);


//        size++;
        // v3
        add(0,e);


    }

    // 在链表的index(0-based) 位置添加新的元素e
    // 在链表中不是一个常用的操作，练习用：)
    public void add(int index,E e) {
        if (index<0 || index >size)
            throw  new IllegalArgumentException("Add failed. Illagal index.");
//        if (index == 0)
//            addFirst(e);
//        else {
            Node prev = dummyhead;
            for (int i = 0; i < index; i++)
                prev = prev.next;
//            Node node = new Node(e);
//            node.next = prev.next;
//            prev.next=node;

            prev.next = new Node(e,prev.next);

            size++;
//        }
    }
    // --- 递归实现链表添加 start  --- //
//    public void add(int index,E e) {
//        Head = add(head,index,e);
//         size++；
//    }
//
//    // 在以node为头结点的链表的index位置插入元素e，递归算法
//    private Node add(Node node,int index,E e) {
//        if (index == 0)
//            return  new Node(e, node);
//        node.next = add(node.next,index-1,e);
//        return  node;
//    }
    // --- 递归实现链表添加 end   --- //





    // 在链表末尾添加新元素e
    public void addLast(E e) {
        add(size,e);
    }

    // 获取链表的第index(0-based) 个位置的元素
    // 在链表中不是一个常用的操作，练习用：)
    public E get(int index) {
        if (index<0||index>=size)
            throw new IllegalArgumentException("Get failed. Illegal index.");
        Node cur =dummyhead.next;
        for (int i = 0; i < index; i++)
            cur = cur.next;
        return  cur.e;
    }

    // 获取链表的第一个元素
    public E getFirst() {
        return get(0);
    }

    // 获取链表的最后一个元素
    public E getLast() {
        return get(size-1);
    }

    // 修改链表的第index(0-based) 个位置的元素为e
    // 在链表中不是一个常用的操作，练习用：)
    public void set(int index,E e) {
        if (index<0||index>=size)
            throw new IllegalArgumentException("Get failed. Illegal index.");
        Node cur =dummyhead.next;
        for (int i = 0; i < index; i++)
            cur = cur.next;
        cur.e = e;
    }

    // 查找链表中是否有元素e
    public boolean contains(E e) {
        Node cur = dummyhead.next;
        while (cur!=null) {
            if (cur.e.equals(e))
                return  true;
            cur =cur.next;
        }
        return false;
    }

    // 从链表中删除第index(0-based)位置的元素,返回删除的元素
    // 在链表中不是一个常用的操作，练习用：)
    public E remove(int index) {
        if (index<0||index>=size)
            throw new IllegalArgumentException("Remove failed. Illegal index.");
        Node prev = dummyhead;
        for (int i = 0; i < index; i++)
            prev = prev.next;

        Node retNode =  prev.next;
        prev.next = retNode.next;
        retNode.next =null;
        size--;

        return  retNode.e;
    }

    // 从链表中删除第一个元素，返回删除的元素
    public E removeFirst() {
        return remove(0);
    }

    // 从链表中删除最后一个元素，返回删除元素
    public E removeLast() {
        return  remove(size-1);
    }

    // 从链表中删除元素e
    public void removeElement(E e) {
        Node prev = dummyhead;
        while (prev.next != null) {
            if (prev.next.e.equals(e))
                break;
            prev = prev.next;
        }
        if (prev.next!=null) {
            Node delNode = prev.next;
            prev.next = delNode.next;
            delNode.next = null;
        }
    }


    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        Node cur =dummyhead.next;
        while (cur!=null) {
            sb.append(cur+"->");
            cur = cur.next;
        }
//        for (Node cur = dummyhead.next;cur!=null;cur.next)
//            sb.append(cur+"->");
        sb.append("NULL");
        return sb.toString();
    }

    public static void main(String[] args) {
        LinkedList<Integer> linkedList = new LinkedList<>();
        for (int i = 0; i < 5; i++) {
            linkedList.addFirst(i);
            System.out.println(linkedList);
        }
        linkedList.add(2,666);
        System.out.println(linkedList);
        linkedList.remove(2);
        System.out.println(linkedList);
        linkedList.removeFirst();
        System.out.println(linkedList);
        linkedList.removeLast();
        System.out.println(linkedList);
    }
}
